//在给定的 m x n 网格
// grid 中，每个单元格可以有以下三个值之一： 
//
// 
// 值 0 代表空单元格； 
// 值 1 代表新鲜橘子； 
// 值 2 代表腐烂的橘子。 
// 
//
// 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 
//
// 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
//输出：-1
//解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
// 
//
// 示例 3： 
//
// 
//输入：grid = [[0,2]]
//输出：0
//解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 10 
// grid[i][j] 仅为 0、1 或 2 
// 
//
// Related Topics 广度优先搜索 数组 矩阵 👍 737 👎 0


package LeetCode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-08-23 00:57:09
 * @description 994.腐烂的橘子
 */
public class RottingOranges{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new RottingOranges().new Solution();
		  int[][]grid={{2,1,1},{1,1,0},{0,1,1}};
		 System.out.println(solution.orangesRotting(grid));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*广度优先，时间omn  空间omn*/
    public int orangesRotting(int[][] grid) {
		int m=grid.length;
		int n=grid[0].length;
		Queue<int []> q = new LinkedList<>();
		int [] dx={-1,1,0,0};
		int [] dy={0,0,-1,1};
		int step=0;//感染次数
		int flash=0;//新鲜
		//把腐烂橘子入队，并记录新鲜橘子数
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(grid[i][j]==1){
					flash++;
				}
				if(grid[i][j]==2){
					q.offer(new int[]{i,j});
				}
			}
		}
		//遍历，感染
		while (flash>0&&!q.isEmpty()){
			step++;
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int[] poll = q.poll();
				for (int j = 0; j < 4; j++) {
					int x=poll[0]+dx[j];
					int y=poll[1]+dy[j];
					if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
						grid[x][y]=2;
						q.offer(new int[]{x,y});
						flash--;
					}
				}
			}
		}
		//感染完还有新鲜的
		if(flash>0) return -1;
		return step;

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
